package com.linchong.heap.hard;

import java.util.PriorityQueue;

/**
 * @author linchong
 * @version 1.0
 * @Date: 2020-12-01 20:10
 * @Description: FindMedianFromDataStream$295-数据流中的中位数
 * 中位数是有序列表中间的数。如果列表长度是偶数，中位数则是中间两个数的平均值。
 * <p>
 * 例如，
 * <p>
 * [2,3,4] 的中位数是 3
 * <p>
 * [2,3] 的中位数是 (2 + 3) / 2 = 2.5
 * <p>
 * 设计一个支持以下两种操作的数据结构：
 * <p>
 * void addNum(int num) - 从数据流中添加一个整数到数据结构中。
 * double findMedian() - 返回目前所有元素的中位数。
 * 示例：
 * <p>
 * addNum(1)
 * addNum(2)
 * findMedian() -> 1.5
 * addNum(3)
 * findMedian() -> 2
 * 进阶:
 * <p>
 * 如果数据流中所有整数都在 0 到 100 范围内，你将如何优化你的算法？
 * 如果数据流中 99% 的整数都在 0 到 100 范围内，你将如何优化你的算法？
 */
@SuppressWarnings("unused")
public class FindMedianFromDataStream {

	static class MedianFinder {

		//最大堆
		private PriorityQueue<Integer> maxHeap;

		//最小堆
		private PriorityQueue<Integer> minHeap;

		//计数，大顶堆与小顶堆的元素差距不能超过1.
		private int counter = 0;

		/**
		 * initialize your data structure here.
		 */
		public MedianFinder() {
			minHeap = new PriorityQueue<>();
			maxHeap = new PriorityQueue<>((i, j) -> j - i);
		}

		public void addNum(int num) {
			counter++;
			if(counter%2==0){
				if(!maxHeap.isEmpty()&&num<maxHeap.peek()){
					maxHeap.add(num);
					num = maxHeap.poll();
				}
				minHeap.add(num);
			}else{
				if(!minHeap.isEmpty()&&num>minHeap.peek()){
					minHeap.add(num);
					num=minHeap.poll();
				}
				maxHeap.add(num);
			}
		}

		public double findMedian() {
			if(maxHeap.size()==minHeap.size()) {
				return (maxHeap.peek() + minHeap.peek()) / 2.0;
			}else if(maxHeap.size()>minHeap.size()) {
				return maxHeap.peek() * 1.0;
			}else{
				return minHeap.peek()*1.0;
			}

		}
	}


}
